package lanqiao._02算法训练.page02;

import java.util.Scanner;

/**
 * @author 挚爱之夕
 * @version 1.0
 * @implSpec
 * 问题描述
 * 　　在一个n*n的棋盘中，每个格子中至多放置一个车，且要保证任何两个车都不能相互攻击，有多少中放法(车与车之间是没有差别的)
 * 输入格式
 * 　　包含一个正整数n
 * 输出格式
 * 　　一个整数，表示放置车的方法数
 * 样例输入
 * 2
 * 样例输出
 * 7
 * 【样例解释】一个车都不放为1种，放置一个车有4种，放置2个车有2种。
 * 数据规模和约定
 * 　　n<=8
 * 思路：
 * 不能放在同行同列：
 * vis数组 vis[col] 表示col行已经放置一个车
 * 从 0 - n-1 行放置，每行可选择放或不放
 * 车的数量不定：
 * res = 1 不放为一种
 * 每选择放一个车， 是一种情况 res + 1
 * @since 2022 - 10 - 30 - 23:03
 */
public class _11车的放置 {
}
class Main11{
    static int n;
    static int res;
    static boolean[] visCol;
    public static void main(String[] args){
        Scanner sc = new Scanner(System.in);
        n = sc.nextInt();
        res = 1;
        //visCol[col]记录col行是否放车
        visCol = new boolean[n];
        dfs(0);
        System.out.println(res);
    }
    static void dfs(int row){
        //出口
        if(row >= n) return;
        //考虑在当前行，放置车
        for(int col = 0; col < n; col++){
            if(!visCol[col]){   //可以放在该行
                visCol[col] = true;
                //每放置一个车就得到了一种放法
                res++;
                dfs(row + 1);
                //回溯
                visCol[col] = false;
            }
        }
        //当前行不放车
        dfs(row + 1);
    }
}